home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 May / macformat-024.iso / Shareware City / Developers / nshellmegasource1.50 / mega src / lib / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-26  |  24.8 KB  |  1,043 lines  |  [TEXT/KAHL]
  1. /*
  2.  
  3.  * regcomp and regexec -- regsub and regerror are elsewhere
  4.  * @(#)regexp.c    1.3 of 18 April 87
  5.  *
  6.  *    Copyright (c) 1986 by University of Toronto.
  7.  *    Written by Henry Spencer.  Not derived from licensed software.
  8.  *
  9.  *    Permission is granted to anyone to use this software for any
  10.  *    purpose on any computer system, and to redistribute it freely,
  11.  *    subject to the following restrictions:
  12.  *
  13.  *    1. The author is not responsible for the consequences of use of
  14.  *        this software, no matter how awful, even if they arise
  15.  *        from defects in it.
  16.  *
  17.  *    2. The origin of this software must not be misrepresented, either
  18.  *        by explicit claim or by omission.
  19.  *
  20.  *    3. Altered versions must be plainly marked as such, and must not
  21.  *        be misrepresented as being the original software.
  22.  *
  23.  * Beware that some of this code is subtly aware of the way operator
  24.  * precedence is structured in regular expressions.  Serious changes in
  25.  * regular-expression syntax might require a total rethink.
  26.  
  27.  =
  28.  = Aleration Notice:
  29.  =
  30.  = I went through these files and quickly made them compatible with
  31.  = my nShell environment.  If I made mistakes in my blind rush, I
  32.  = apologize.  Changes include:
  33.  =
  34.  = 1. I combined regexp.h and regmagic.h into a new regexp.h
  35.  = 2. I deleted regmagic.h
  36.  = 3. I renamed regproto.h to regexp.proto.h
  37.  = 4. I removed all references to and code using the DEBUG macro.
  38.  =
  39.  = If you are interested in the inner workings of a regex package, I
  40.  = suggest you get the original "Henry Spencer" distribution.  It is
  41.  = available on a number of archives.  I got mine from the "MacSource"
  42.  = CD.
  43.  =
  44.  = Thanks Henry,
  45.  =
  46.  = John Jensen, Newport Software Development, 11/26/94
  47.  =
  48.  
  49.  */
  50.  
  51. #include    <string.h>
  52. #include    <stdlib.h>
  53.  
  54. #include    "regexp.h"
  55. #include    "regexp.proto.h"
  56.  
  57. /*
  58.  * The "internal use only" fields in regexp.h are present to pass info from
  59.  * compile to execute that permits the execute phase to run lots faster on
  60.  * simple cases.  They are:
  61.  *
  62.  * regstart    char that must begin a match; '\0' if none obvious
  63.  * reganch    is the match anchored (at beginning-of-line only)?
  64.  * regmust    string (pointer into program) that match must include, or NULL
  65.  * regmlen    length of regmust string
  66.  *
  67.  * Regstart and reganch permit very fast decisions on suitable starting points
  68.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  69.  * of lines that cannot possibly match.  The regmust tests are costly enough
  70.  * that regcomp() supplies a regmust only if the r.e. contains something
  71.  * potentially expensive (at present, the only such thing detected is * or +
  72.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  73.  * supplied because the test in regexec() needs it and regcomp() is computing
  74.  * it anyway.
  75.  */
  76.  
  77. /*
  78.  * Structure for regexp "program".  This is essentially a linear encoding
  79.  * of a nondeterministic finite-state machine (aka syntax charts or
  80.  * "railroad normal form" in parsing technology).  Each node is an opcode
  81.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  82.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  83.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  84.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  85.  * opposed to a collection of them) is never concatenated with anything
  86.  * because of operator precedence.)  The operand of some types of node is
  87.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  88.  * particular, the operand of a BRANCH node is the first node of the branch.
  89.  * (NB this is *not* a tree structure:  the tail of the branch connects
  90.  * to the thing following the set of BRANCHes.)  The opcodes are:
  91.  */
  92.  
  93. /* definition    number    opnd?    meaning */
  94. #define    END    0    /* no    End of program. */
  95. #define    BOL    1    /* no    Match "" at beginning of line. */
  96. #define    EOL    2    /* no    Match "" at end of line. */
  97. #define    ANY    3    /* no    Match any one character. */
  98. #define    ANYOF    4    /* str    Match any character in this string. */
  99. #define    ANYBUT    5    /* str    Match any character not in this string. */
  100. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  101. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  102. #define    EXACTLY    8    /* str    Match this string. */
  103. #define    NOTHING    9    /* no    Match empty string. */
  104. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  105. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  106. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  107.             /*    OPEN+1 is number 1, etc. */
  108. #define    CLOSE    30    /* no    Analogous to OPEN. */
  109.  
  110. /*
  111.  * Opcode notes:
  112.  *
  113.  * BRANCH    The set of branches constituting a single choice are hooked
  114.  *        together with their "next" pointers, since precedence prevents
  115.  *        anything being concatenated to any individual branch.  The
  116.  *        "next" pointer of the last BRANCH in a choice points to the
  117.  *        thing following the whole choice.  This is also where the
  118.  *        final "next" pointer of each individual branch points; each
  119.  *        branch starts with the operand node of a BRANCH node.
  120.  *
  121.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  122.  *        exists to make loop structures possible.
  123.  *
  124.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  125.  *        BRANCH structures using BACK.  Simple cases (one character
  126.  *        per match) are implemented with STAR and PLUS for speed
  127.  *        and to minimize recursive plunges.
  128.  *
  129.  * OPEN,CLOSE    ...are numbered at compile time.
  130.  */
  131.  
  132. /*
  133.  * A node is one char of opcode followed by two chars of "next" pointer.
  134.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  135.  * value is a positive offset from the opcode of the node containing it.
  136.  * An operand, if any, simply follows the node.  (Note that much of the
  137.  * code generation knows about this implicit relationship.)
  138.  *
  139.  * Using two bytes for the "next" pointer is vast overkill for most things,
  140.  * but allows patterns to get big without disasters.
  141.  */
  142. #define    OP(p)    (*(p))
  143. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  144. #define    OPERAND(p)    ((p) + 3)
  145.  
  146. /*
  147.  * See regmagic.h for one further detail of program structure.
  148.  */
  149.  
  150.  
  151. /*
  152.  * Utility definitions.
  153.  */
  154. #ifndef CHARBITS
  155. #define    UCHARAT(p)    ((long)*(unsigned char *)(p))
  156. #else
  157. #define    UCHARAT(p)    ((long)*(p)&CHARBITS)
  158. #endif
  159.  
  160. #define    FAIL(m)    { regerror(m); return(NULL); }
  161. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  162. #define    META    "^$.[()|?+*\\"
  163.  
  164. /*
  165.  * Flags to be passed up and down.
  166.  */
  167. #define    HASWIDTH    01    /* Known never to match null string. */
  168. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  169. #define    SPSTART        04    /* Starts with * or +. */
  170. #define    WORST        0    /* Worst case. */
  171.  
  172. /*
  173.  * Global work variables for regcomp().
  174.  */
  175. static char *regparse;        /* Input-scan pointer. */
  176. static long regnpar;        /* () count. */
  177. static char regdummy;
  178. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  179. static long regsize;        /* Code size. */
  180.  
  181. /*
  182.  - regcomp - compile a regular expression into internal code
  183.  *
  184.  * We can't allocate space until we know how big the compiled form will be,
  185.  * but we can't compile it (and thus know how big it is) until we've got a
  186.  * place to put the code.  So we cheat:  we compile it twice, once with code
  187.  * generation turned off and size counting turned on, and once "for real".
  188.  * This also means that we don't allocate space until we are sure that the
  189.  * thing really will compile successfully, and we never have to move the
  190.  * code and thus invalidate pointers into it.  (Note that it has to be in
  191.  * one piece because free() must be able to free it all.)
  192.  *
  193.  * Beware that the optimization-preparation code in here knows about some
  194.  * of the structure of the compiled regexp.
  195.  */
  196. regexp *
  197. regcomp(exp)
  198. char *exp;
  199. {
  200.     register regexp *r;
  201.     register char *scan;
  202.     register char *longest;
  203.     register long len;
  204.     long flags;
  205.  
  206.     if (exp == NULL)
  207.         FAIL("NULL argument");
  208.  
  209.     /* First pass: determine size, legality. */
  210.     regparse = exp;
  211.     regnpar = 1;
  212.     regsize = 0L;
  213.     regcode = ®dummy;
  214.     regc(MAGIC);
  215.     if (reg(0, &flags) == NULL)
  216.         return(NULL);
  217.  
  218.     /* Small enough for pointer-storage convention? */
  219.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  220.         FAIL("regexp too big");
  221.  
  222.     /* Allocate space. */
  223.     r = (regexp *)NewPtr((sizeof(regexp) + (unsigned)regsize));
  224.     if (r == NULL)
  225.         FAIL("out of space");
  226.  
  227.     /* Second pass: emit code. */
  228.     regparse = exp;
  229.     regnpar = 1;
  230.     regcode = r->program;
  231.     regc(MAGIC);
  232.     if (reg(0, &flags) == NULL)
  233.         return(NULL);
  234.  
  235.     /* Dig out information for optimizations. */
  236.     r->regstart = '\0';    /* Worst-case defaults. */
  237.     r->reganch = 0;
  238.     r->regmust = NULL;
  239.     r->regmlen = 0;
  240.     scan = r->program+1;            /* First BRANCH. */
  241.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  242.         scan = OPERAND(scan);
  243.  
  244.         /* Starting-point info. */
  245.         if (OP(scan) == EXACTLY)
  246.             r->regstart = *OPERAND(scan);
  247.         else if (OP(scan) == BOL)
  248.             r->reganch++;
  249.  
  250.         /*
  251.          * If there's something expensive in the r.e., find the
  252.          * longest literal string that must appear and make it the
  253.          * regmust.  Resolve ties in favor of later strings, since
  254.          * the regstart check works with the beginning of the r.e.
  255.          * and avoiding duplication strengthens checking.  Not a
  256.          * strong reason, but sufficient in the absence of others.
  257.          */
  258.         if (flags&SPSTART) {
  259.             longest = NULL;
  260.             len = 0;
  261.             for (; scan != NULL; scan = regnext(scan))
  262.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  263.                     longest = OPERAND(scan);
  264.                     len = strlen(OPERAND(scan));
  265.                 }
  266.             r->regmust = longest;
  267.             r->regmlen = len;
  268.         }
  269.     }
  270.  
  271.     return(r);
  272. }
  273.  
  274. /*
  275.  - reg - regular expression, i.e. main body or parenthesized thing
  276.  *
  277.  * Caller must absorb opening parenthesis.
  278.  *
  279.  * Combining parenthesis handling with the base level of regular expression
  280.  * is a trifle forced, but the need to tie the tails of the branches to what
  281.  * follows makes it hard to avoid.
  282.  */
  283. static char *reg(long paren, long *flagp)
  284. {
  285.     register char *ret;
  286.     register char *br;
  287.     register char *ender;
  288.     register long parno;
  289.     long flags;
  290.  
  291.     *flagp = HASWIDTH;    /* Tentatively. */
  292.  
  293.     /* Make an OPEN node, if parenthesized. */
  294.     if (paren) {
  295.         if (regnpar >= NSUBEXP)
  296.             FAIL("too many ()");
  297.         parno = regnpar;
  298.         regnpar++;
  299.         ret = regnode(OPEN+parno);
  300.     } else
  301.         ret = NULL;
  302.  
  303.     /* Pick up the branches, linking them together. */
  304.     br = regbranch(&flags);
  305.     if (br == NULL)
  306.         return(NULL);
  307.     if (ret != NULL)
  308.         regtail(ret, br);    /* OPEN -> first. */
  309.     else
  310.         ret = br;
  311.     if (!(flags&HASWIDTH))
  312.         *flagp &= ~HASWIDTH;
  313.     *flagp |= flags&SPSTART;
  314.     while (*regparse == '|') {
  315.         regparse++;
  316.         br = regbranch(&flags);
  317.         if (br == NULL)
  318.             return(NULL);
  319.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  320.         if (!(flags&HASWIDTH))
  321.             *flagp &= ~HASWIDTH;
  322.         *flagp |= flags&SPSTART;
  323.     }
  324.  
  325.     /* Make a closing node, and hook it on the end. */
  326.     ender = regnode((paren) ? CLOSE+parno : END);    
  327.     regtail(ret, ender);
  328.  
  329.     /* Hook the tails of the branches to the closing node. */
  330.     for (br = ret; br != NULL; br = regnext(br))
  331.         regoptail(br, ender);
  332.  
  333.     /* Check for proper termination. */
  334.     if (paren && *regparse++ != ')') {
  335.         FAIL("unmatched ()");
  336.     } else if (!paren && *regparse != '\0') {
  337.         if (*regparse == ')') {
  338.             FAIL("unmatched ()");
  339.         } else
  340.             FAIL("junk on end");    /* "Can't happen". */
  341.         /* NOTREACHED */
  342.     }
  343.  
  344.     return(ret);
  345. }
  346.  
  347. /*
  348.  - regbranch - one alternative of an | operator
  349.  *
  350.  * Implements the concatenation operator.
  351.  */
  352. static char *regbranch(long *flagp)
  353. {
  354.     register char *ret;
  355.     register char *chain;
  356.     register char *latest;
  357.     long flags;
  358.  
  359.     *flagp = WORST;        /* Tentatively. */
  360.  
  361.     ret = regnode(BRANCH);
  362.     chain = NULL;
  363.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  364.         latest = regpiece(&flags);
  365.         if (latest == NULL)
  366.             return(NULL);
  367.         *flagp |= flags&HASWIDTH;
  368.         if (chain == NULL)    /* First piece. */
  369.             *flagp |= flags&SPSTART;
  370.         else
  371.             regtail(chain, latest);
  372.         chain = latest;
  373.     }
  374.     if (chain == NULL)    /* Loop ran zero times. */
  375.         (void) regnode(NOTHING);
  376.  
  377.     return(ret);
  378. }
  379.  
  380. /*
  381.  - regpiece - something followed by possible [*+?]
  382.  *
  383.  * Note that the branching code sequences used for ? and the general cases
  384.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  385.  * both the endmarker for their branch list and the body of the last branch.
  386.  * It might seem that this node could be dispensed with entirely, but the
  387.  * endmarker role is not redundant.
  388.  */
  389. static char *regpiece(long *flagp)
  390. {
  391.     register char *ret;
  392.     register char op;
  393.     register char *next;
  394.     long flags;
  395.  
  396.     ret = regatom(&flags);
  397.     if (ret == NULL)
  398.         return(NULL);
  399.  
  400.     op = *regparse;
  401.     if (!ISMULT(op)) {
  402.         *flagp = flags;
  403.         return(ret);
  404.     }
  405.  
  406.     if (!(flags&HASWIDTH) && op != '?')
  407.         FAIL("*+ operand could be empty");
  408.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  409.  
  410.     if (op == '*' && (flags&SIMPLE))
  411.         reginsert(STAR, ret);
  412.     else if (op == '*') {
  413.         /* Emit x* as (x&|), where & means "self". */
  414.         reginsert(BRANCH, ret);            /* Either x */
  415.         regoptail(ret, regnode(BACK));        /* and loop */
  416.         regoptail(ret, ret);            /* back */
  417.         regtail(ret, regnode(BRANCH));        /* or */
  418.         regtail(ret, regnode(NOTHING));        /* null. */
  419.     } else if (op == '+' && (flags&SIMPLE))
  420.         reginsert(PLUS, ret);
  421.     else if (op == '+') {
  422.         /* Emit x+ as x(&|), where & means "self". */
  423.         next = regnode(BRANCH);            /* Either */
  424.         regtail(ret, next);
  425.         regtail(regnode(BACK), ret);        /* loop back */
  426.         regtail(next, regnode(BRANCH));        /* or */
  427.         regtail(ret, regnode(NOTHING));        /* null. */
  428.     } else if (op == '?') {
  429.         /* Emit x? as (x|) */
  430.         reginsert(BRANCH, ret);            /* Either x */
  431.         regtail(ret, regnode(BRANCH));        /* or */
  432.         next = regnode(NOTHING);        /* null. */
  433.         regtail(ret, next);
  434.         regoptail(ret, next);
  435.     }
  436.     regparse++;
  437.     if (ISMULT(*regparse))
  438.         FAIL("nested *?+");
  439.  
  440.     return(ret);
  441. }
  442.  
  443. /*
  444.  - regatom - the lowest level
  445.  *
  446.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  447.  * it can turn them into a single node, which is smaller to store and
  448.  * faster to run.  Backslashed characters are exceptions, each becoming a
  449.  * separate node; the code is simpler that way and it's not worth fixing.
  450.  */
  451. static char *regatom(long *flagp)
  452. {
  453.     register char *ret;
  454.     long flags;
  455.  
  456.     *flagp = WORST;        /* Tentatively. */
  457.  
  458.     switch (*regparse++) {
  459.     case '^':
  460.         ret = regnode(BOL);
  461.         break;
  462.     case '$':
  463.         ret = regnode(EOL);
  464.         break;
  465.     case '.':
  466.         ret = regnode(ANY);
  467.         *flagp |= HASWIDTH|SIMPLE;
  468.         break;
  469.     case '[': {
  470.             register long class;
  471.             register long classend;
  472.  
  473.             if (*regparse == '^') {    /* Complement of range. */
  474.                 ret = regnode(ANYBUT);
  475.                 regparse++;
  476.             } else
  477.                 ret = regnode(ANYOF);
  478.             if (*regparse == ']' || *regparse == '-')
  479.                 regc(*regparse++);
  480.             while (*regparse != '\0' && *regparse != ']') {
  481.                 if (*regparse == '-') {
  482.                     regparse++;
  483.                     if (*regparse == ']' || *regparse == '\0')
  484.                         regc('-');
  485.                     else {
  486.                         class = UCHARAT(regparse-2)+1;
  487.                         classend = UCHARAT(regparse);
  488.                         if (class > classend+1)
  489.                             FAIL("invalid [] range");
  490.                         for (; class <= classend; class++)
  491.                             regc(class);
  492.                         regparse++;
  493.                     }
  494.                 } else
  495.                     regc(*regparse++);
  496.             }
  497.             regc('\0');
  498.             if (*regparse != ']')
  499.                 FAIL("unmatched []");
  500.             regparse++;
  501.             *flagp |= HASWIDTH|SIMPLE;
  502.         }
  503.         break;
  504.     case '(':
  505.         ret = reg(1, &flags);
  506.         if (ret == NULL)
  507.             return(NULL);
  508.         *flagp |= flags&(HASWIDTH|SPSTART);
  509.         break;
  510.     case '\0':
  511.     case '|':
  512.     case ')':
  513.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  514.         break;
  515.     case '?':
  516.     case '+':
  517.     case '*':
  518.         FAIL("?+* follows nothing");
  519.         break;
  520.     case '\\':
  521.         if (*regparse == '\0')
  522.             FAIL("trailing \\");
  523.         ret = regnode(EXACTLY);
  524.         regc(*regparse++);
  525.         regc('\0');
  526.         *flagp |= HASWIDTH|SIMPLE;
  527.         break;
  528.     default: {
  529.             register long len;
  530.             register char ender;
  531.  
  532.             regparse--;
  533.             len = strcspn(regparse, META);
  534.             if (len <= 0)
  535.                 FAIL("internal disaster");
  536.             ender = *(regparse+len);
  537.             if (len > 1 && ISMULT(ender))
  538.                 len--;        /* Back off clear of ?+* operand. */
  539.             *flagp |= HASWIDTH;
  540.             if (len == 1)
  541.                 *flagp |= SIMPLE;
  542.             ret = regnode(EXACTLY);
  543.             while (len > 0) {
  544.                 regc(*regparse++);
  545.                 len--;
  546.             }
  547.             regc('\0');
  548.         }
  549.         break;
  550.     }
  551.  
  552.     return(ret);
  553. }
  554.  
  555. /*
  556.  - regnode - emit a node
  557.  */
  558. static char * regnode(char op)
  559. {
  560.     register char *ret;
  561.     register char *ptr;
  562.  
  563.     ret = regcode;
  564.     if (ret == ®dummy) {
  565.         regsize += 3;
  566.         return(ret);
  567.     }
  568.  
  569.     ptr = ret;
  570.     *ptr++ = op;
  571.     *ptr++ = '\0';        /* Null "next" pointer. */
  572.     *ptr++ = '\0';
  573.     regcode = ptr;
  574.  
  575.     return(ret);
  576. }
  577.  
  578. /*
  579.  - regc - emit (if appropriate) a byte of code
  580.  */
  581. static void regc(char b)
  582. {
  583.     if (regcode != ®dummy)
  584.         *regcode++ = b;
  585.     else
  586.         regsize++;
  587. }
  588.  
  589. /*
  590.  - reginsert - insert an operator in front of already-emitted operand
  591.  *
  592.  * Means relocating the operand.
  593.  */
  594. static void reginsert(char op, char *opnd)
  595. {
  596.     register char *src;
  597.     register char *dst;
  598.     register char *place;
  599.  
  600.     if (regcode == ®dummy) {
  601.         regsize += 3;
  602.         return;
  603.     }
  604.  
  605.     src = regcode;
  606.     regcode += 3;
  607.     dst = regcode;
  608.     while (src > opnd)
  609.         *--dst = *--src;
  610.  
  611.     place = opnd;        /* Op node, where operand used to be. */
  612.     *place++ = op;
  613.     *place++ = '\0';
  614.     *place++ = '\0';
  615. }
  616.  
  617. /*
  618.  - regtail - set the next-pointer at the end of a node chain
  619.  */
  620. static void regtail(char *p, char *val)
  621. {
  622.     register char *scan;
  623.     register char *temp;
  624.     register long offset;
  625.  
  626.     if (p == ®dummy)
  627.         return;
  628.  
  629.     /* Find last node. */
  630.     scan = p;
  631.     for (;;) {
  632.         temp = regnext(scan);
  633.         if (temp == NULL)
  634.             break;
  635.         scan = temp;
  636.     }
  637.  
  638.     if (OP(scan) == BACK)
  639.         offset = scan - val;
  640.     else
  641.         offset = val - scan;
  642.     *(scan+1) = (offset>>8)&0377;
  643.     *(scan+2) = offset&0377;
  644. }
  645.  
  646. /*
  647.  - regoptail - regtail on operand of first argument; nop if operandless
  648.  */
  649. static void regoptail(char *p, char *val)
  650. {
  651.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  652.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  653.         return;
  654.     regtail(OPERAND(p), val);
  655. }
  656.  
  657. /*
  658.  * regexec and friends
  659.  */
  660.  
  661. /*
  662.  * Global work variables for regexec().
  663.  */
  664. static char *reginput;        /* String-input pointer. */
  665. static char *regbol;        /* Beginning of input, for ^ check. */
  666. static char **regstartp;    /* Pointer to startp array. */
  667. static char **regendp;        /* Ditto for endp. */
  668.  
  669. /*
  670.  - regexec - match a regexp against a string
  671.  */
  672. long regexec(register regexp *prog, register char *string)
  673. {
  674.     register char *s;
  675.     extern char *strchr();
  676.  
  677.     /* Be paranoid... */
  678.     if (prog == NULL || string == NULL) {
  679.         regerror("NULL parameter");
  680.         return(0);
  681.     }
  682.  
  683.     /* Check validity of program. */
  684.     if (UCHARAT(prog->program) != MAGIC) {
  685.         regerror("corrupted program");
  686.         return(0);
  687.     }
  688.  
  689.     /* If there is a "must appear" string, look for it. */
  690.     if (prog->regmust != NULL) {
  691.         s = string;
  692.         while ((s = strchr(s, prog->regmust[0])) != NULL) {
  693.             if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  694.                 break;    /* Found it. */
  695.             s++;
  696.         }
  697.         if (s == NULL)    /* Not present. */
  698.             return(0);
  699.     }
  700.  
  701.     /* Mark beginning of line for ^ . */
  702.     regbol = string;
  703.  
  704.     /* Simplest case:  anchored match need be tried only once. */
  705.     if (prog->reganch)
  706.         return(regtry(prog, string));
  707.  
  708.     /* Messy cases:  unanchored match. */
  709.     s = string;
  710.     if (prog->regstart != '\0')
  711.         /* We know what char it must start with. */
  712.         while ((s = strchr(s, prog->regstart)) != NULL) {
  713.             if (regtry(prog, s))
  714.                 return(1);
  715.             s++;
  716.         }
  717.     else
  718.         /* We don't -- general case. */
  719.         do {
  720.             if (regtry(prog, s))
  721.                 return(1);
  722.         } while (*s++ != '\0');
  723.  
  724.     /* Failure. */
  725.     return(0);
  726. }
  727.  
  728. /*
  729.  - regtry - try match at specific point
  730.  */
  731.  
  732. /* Returns 0 = failure, 1 = success */
  733.  
  734. static long regtry(regexp *prog, char *string)
  735. {
  736.     register long i;
  737.     register char **sp;
  738.     register char **ep;
  739.  
  740.     reginput = string;
  741.     regstartp = prog->startp;
  742.     regendp = prog->endp;
  743.  
  744.     sp = prog->startp;
  745.     ep = prog->endp;
  746.     for (i = NSUBEXP; i > 0; i--) {
  747.         *sp++ = NULL;
  748.         *ep++ = NULL;
  749.     }
  750.     if (regmatch(prog->program + 1)) {
  751.         prog->startp[0] = string;
  752.         prog->endp[0] = reginput;
  753.         return(1);
  754.     } else
  755.         return(0);
  756. }
  757.  
  758. /*
  759.  - regmatch - main matching routine
  760.  *
  761.  * Conceptually the strategy is simple:  check to see whether the current
  762.  * node matches, call self recursively to see whether the rest matches,
  763.  * and then act accordingly.  In practice we make some effort to avoid
  764.  * recursion, in particular by going through "ordinary" nodes (that don't
  765.  * need to know whether the rest of the match failed) by a loop instead of
  766.  * by recursion.
  767.  */
  768.  
  769. /* Returns 0 = failure, 1 = success */
  770.  
  771. static long regmatch(char *prog)
  772. {
  773.     register char *scan;    /* Current node. */
  774.     char *next;        /* Next node. */
  775.     extern char *strchr();
  776.  
  777.     scan = prog;
  778.  
  779.     while (scan != NULL) {
  780.  
  781.         next = regnext(scan);
  782.  
  783.         switch (OP(scan)) {
  784.         case BOL:
  785.             if (reginput != regbol)
  786.                 return(0);
  787.             break;
  788.         case EOL:
  789.             if (*reginput != '\0')
  790.                 return(0);
  791.             break;
  792.         case ANY:
  793.             if (*reginput == '\0')
  794.                 return(0);
  795.             reginput++;
  796.             break;
  797.         case EXACTLY: {
  798.                 register long len;
  799.                 register char *opnd;
  800.  
  801.                 opnd = OPERAND(scan);
  802.                 /* Inline the first character, for speed. */
  803.                 if (*opnd != *reginput)
  804.                     return(0);
  805.                 len = strlen(opnd);
  806.                 if (len > 1 && strncmp(opnd, reginput, len) != 0)
  807.                     return(0);
  808.                 reginput += len;
  809.             }
  810.             break;
  811.         case ANYOF:
  812.             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  813.                 return(0);
  814.             reginput++;
  815.             break;
  816.         case ANYBUT:
  817.             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  818.                 return(0);
  819.             reginput++;
  820.             break;
  821.         case NOTHING:
  822.             break;
  823.         case BACK:
  824.             break;
  825.         case OPEN+1:
  826.         case OPEN+2:
  827.         case OPEN+3:
  828.         case OPEN+4:
  829.         case OPEN+5:
  830.         case OPEN+6:
  831.         case OPEN+7:
  832.         case OPEN+8:
  833.         case OPEN+9: {
  834.                 register long no;
  835.                 register char *save;
  836.  
  837.                 no = OP(scan) - OPEN;
  838.                 save = reginput;
  839.  
  840.                 if (regmatch(next)) {
  841.                     /*
  842.                      * Don't set startp if some later
  843.                      * invocation of the same parentheses
  844.                      * already has.
  845.                      */
  846.                     if (regstartp[no] == NULL)
  847.                         regstartp[no] = save;
  848.                     return(1);
  849.                 } else
  850.                     return(0);
  851.             }
  852.             break;
  853.         case CLOSE+1:
  854.         case CLOSE+2:
  855.         case CLOSE+3:
  856.         case CLOSE+4:
  857.         case CLOSE+5:
  858.         case CLOSE+6:
  859.         case CLOSE+7:
  860.         case CLOSE+8:
  861.         case CLOSE+9: {
  862.                 register long no;
  863.                 register char *save;
  864.  
  865.                 no = OP(scan) - CLOSE;
  866.                 save = reginput;
  867.  
  868.                 if (regmatch(next)) {
  869.                     /*
  870.                      * Don't set endp if some later
  871.                      * invocation of the same parentheses
  872.                      * already has.
  873.                      */
  874.                     if (regendp[no] == NULL)
  875.                         regendp[no] = save;
  876.                     return(1);
  877.                 } else
  878.                     return(0);
  879.             }
  880.             break;
  881.         case BRANCH: {
  882.                 register char *save;
  883.  
  884.                 if (OP(next) != BRANCH)        /* No choice. */
  885.                     next = OPERAND(scan);    /* Avoid recursion. */
  886.                 else {
  887.                     do {
  888.                         save = reginput;
  889.                         if (regmatch(OPERAND(scan)))
  890.                             return(1);
  891.                         reginput = save;
  892.                         scan = regnext(scan);
  893.                     } while (scan != NULL && OP(scan) == BRANCH);
  894.                     return(0);
  895.                     /* NOTREACHED */
  896.                 }
  897.             }
  898.             break;
  899.         case STAR:
  900.         case PLUS: {
  901.                 register char nextch;
  902.                 register long no;
  903.                 register char *save;
  904.                 register long min;
  905.  
  906.                 /*
  907.                  * Lookahead to avoid useless match attempts
  908.                  * when we know what character comes next.
  909.                  */
  910.                 nextch = '\0';
  911.                 if (OP(next) == EXACTLY)
  912.                     nextch = *OPERAND(next);
  913.                 min = (OP(scan) == STAR) ? 0 : 1;
  914.                 save = reginput;
  915.                 no = regrepeat(OPERAND(scan));
  916.                 while (no >= min) {
  917.                     /* If it could work, try it. */
  918.                     if (nextch == '\0' || *reginput == nextch)
  919.                         if (regmatch(next))
  920.                             return(1);
  921.                     /* Couldn't or didn't -- back up. */
  922.                     no--;
  923.                     reginput = save + no;
  924.                 }
  925.                 return(0);
  926.             }
  927.             break;
  928.         case END:
  929.             return(1);    /* Success! */
  930.             break;
  931.         default:
  932.             regerror("memory corruption");
  933.             return(0);
  934.             break;
  935.         }
  936.  
  937.         scan = next;
  938.     }
  939.  
  940.     /*
  941.      * We get here only if there's trouble -- normally "case END" is
  942.      * the terminating point.
  943.      */
  944.     regerror("corrupted pointers");
  945.     return(0);
  946. }
  947.  
  948. /*
  949.  - regrepeat - repeatedly match something simple, report how many
  950.  */
  951. static long regrepeat(char *p)
  952. {
  953.     register long count = 0;
  954.     register char *scan;
  955.     register char *opnd;
  956.  
  957.     scan = reginput;
  958.     opnd = OPERAND(p);
  959.     switch (OP(p)) {
  960.     case ANY:
  961.         count = strlen(scan);
  962.         scan += count;
  963.         break;
  964.     case EXACTLY:
  965.         while (*opnd == *scan) {
  966.             count++;
  967.             scan++;
  968.         }
  969.         break;
  970.     case ANYOF:
  971.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  972.             count++;
  973.             scan++;
  974.         }
  975.         break;
  976.     case ANYBUT:
  977.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  978.             count++;
  979.             scan++;
  980.         }
  981.         break;
  982.     default:        /* Oh dear.  Called inappropriately. */
  983.         regerror("internal foulup");
  984.         count = 0;    /* Best compromise. */
  985.         break;
  986.     }
  987.     reginput = scan;
  988.  
  989.     return(count);
  990. }
  991.  
  992. /*
  993.  - regnext - dig the "next" pointer out of a node
  994.  */
  995. static char *regnext( register char *p )
  996. {
  997.     register long offset;
  998.  
  999.     if (p == ®dummy)
  1000.         return(NULL);
  1001.  
  1002.     offset = NEXT(p);
  1003.     if (offset == 0)
  1004.         return(NULL);
  1005.  
  1006.     if (OP(p) == BACK)
  1007.         return(p-offset);
  1008.     else
  1009.         return(p+offset);
  1010. }
  1011.  
  1012. /*
  1013.  * The following is provided for those people who do not have strcspn() in
  1014.  * their C libraries.  They should get off their butts and do something
  1015.  * about it; at least one public-domain implementation of those (highly
  1016.  * useful) string routines has been published on Usenet.
  1017.  */
  1018. #ifdef STRCSPN
  1019. /*
  1020.  * strcspn - find length of initial segment of s1 consisting entirely
  1021.  * of characters not from s2
  1022.  */
  1023.  
  1024. static long
  1025. strcspn(s1, s2)
  1026. char *s1;
  1027. char *s2;
  1028. {
  1029.     register char *scan1;
  1030.     register char *scan2;
  1031.     register long count;
  1032.  
  1033.     count = 0;
  1034.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1035.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1036.             if (*scan1 == *scan2++)
  1037.                 return(count);
  1038.         count++;
  1039.     }
  1040.     return(count);
  1041. }
  1042. #endif
  1043.